/**
 * @author SaoE
 * @date 2025/2/20 21:10
 */
public class _42 {
    class Solution {
        public int trap(int[] height) {
            int length = height.length;
            if (length <= 2) return 0;
            int[] maxLeft = new int[length];
            int[] maxRight = new int[length];

            // 记录每个柱子左边柱子最大高度
            maxLeft[0] = height[0];
            for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);

            // 记录每个柱子右边柱子最大高度
            maxRight[length - 1] = height[length - 1];
            for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);

            // 求和
            int sum = 0;
            for (int i = 0; i < length; i++) {
                int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
                if (count > 0) sum += count;
            }
            return sum;
        }
    }
}
